package leetcode.剑指offer.后40;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/2 9:24
 * @description :https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 */
public class 剑指_62_圆圈中最后剩下的数字 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.lastRemaining(100000, 3));

    }

    class Solution {
        public int lastRemaining(int n, int m) {
            return f(n, m);
        }

        private int f(int n, int m) {
            if (n == 1) return 0;
            //n - 1个人时出圈的人
            int x = f(n - 1, m);
            //那么第n个出圈的人应该就是从x 开始 数m个
            return (x + m) % n;
        }
    }

    //数学 + 迭代
    /*
    class Solution {
        public int lastRemaining(int n, int m) {
            int f = 0;
            for (int i = 2; i <= n; i++) {
                f = (f + m) % i;
            }
            return f;
        }
    }
     */
}
